Half of the coalition forces casualties in the Iraq and Afghanistan wars are attributed to land mines and improvised explosive devices (IEDs). Consequently, a critical goal of the US Army is to develop robust and effective land-mines/IED detection systems that are deployable in combat environments. Accordingly, there is a desire to create robust algorithms for sub-surface imaging using ground penetrating radar (GPR) data and thus facilitate higher IED detection rates and lower false alarm probabilities.
Referring to the example schematic of FIG. 1, a GPR imaging system transmits signals from an above ground transmitter 102 into the ground of a scene-of-interest (SOI) 104. Signals that are reflected off of objects 106, 108, and 110 in the SOI 104 are received by one or more receivers 112 to generate images that convey relevant information about the objects 106, 108, and 110 (also known as scatters) within the SOI 104. As a transmitted pulse propagates into a SOI 104, reflections occur whenever the pulse encounters changes in the dielectric constant (∈r) of the material through which the pulse propagates. Such a transition occurs, for example, when the radar pulse moving through dirt encounters a metal object such as an IED. The strength of a reflection due to a patch of terrain can be quantified by its reflection coefficient, which is proportional to the overall change in dielectric constant within the patch.
In principle, GPR imaging is well-suited for detecting IEDs and land mines because these targets are expected to have much larger dielectric constants than their surrounding material, such as soil and rocks. It should be noted that for a high frequency transmission pulse (i.e., greater than 3 MHz), the backscattered signal of a target can be well approximated as the sum of the backscattered signals of individual elementary scatterers.
The phrase GPR image reconstruction refers to the process of sub-dividing a SOI into a grid of voxels (i.e., volume elements) and estimating the reflection coefficients of the voxels from radar-return data. Existing image formation techniques for GPR datasets include the delay-and-sum (DAS) or backprojection algorithm and the recursive side-lobe minimization (RSM) algorithm.
The DAS algorithm is probably the most commonly used image formation technique in radar applications because its implementation is straightforward. The DAS algorithm simply estimates the reflectance coefficient of a voxel by coherently adding up, across the receiver-aperture, all the backscatter contributions due to that specific voxel. Although the DAS algorithm is a fast and easy-to-implement method, it tends to produce images that suffer from large side-lobes and poor resolution. The identification of targets with relatively small radar cross section (RCS) is thus difficult from DAS images because targets with large a RCS produce large side-lobes that may obscure adjacent targets with a smaller RCS.
The RSM algorithm is an extension of the DAS algorithm that provides better noise and side-lobe reduction, but no improvement in image resolution. Moreover, results from the RSM algorithm are not always consistent. This may be attributed to the algorithm's use of randomly selected apertures or windows through which a measurement is taken. The requirement for a minimum threshold for probability detection and false alarms would make it difficult to use the RSM algorithm in practical applications.
Both the DAS and RSM algorithms fail to take advantage of valuable a-priori or known information about the scene-of-interest in a GPR context, namely sparsity. More specifically, because only a few scatterers are present in a typical scene-of-interest, in other words most of the backscatter data is zero, it is reasonable to expect better estimates of the reflectance coefficients when this a-priori sparsity assumption is incorporated into the image formation process.
Several linear regression techniques for sparse data set applications are known. Algorithms for sparse linear regression can be roughly divided into the following categories: “greedy” search heuristics, iterative re-weighted linear least squares algorithms, and linear inversion and deconvolution via lp-regularized least-squares.
“Greedy” search heuristics such as projection pursuit, orthogonal matching pursuit (OMP), and the iterative deconvolution algorithm known as CLEAN comprise one category of algorithms for sparse linear regression. Although these algorithms have relatively low computational complexity, regularized least-squares methods have been found to perform better than greedy approaches for sparse reconstruction problems in many radar imaging problems. For instance, the known sparsity learning via iterative minimization (SLIM) algorithm incorporates a-priori sparsity information about the scene-of-interest and provides good results. However, its high computational cost and memory-size requirements may make it inapplicable in real-time settings.
Another known approach to sparse linear regression is the iterative re-weighted linear least-squares (IRLS), where the solution of the mathematical l1-minimization problem is given by solving a sequence of re-weighted l2-minimization problems. A conceptually similar approach is to compute the l0-minimization by solving a sequence of re-weighted l1-minimization problems.
Still another known approach to sparse linear regression are the linear inversion and deconvolution via lp-regularized least-squares (LS) methods. In these methods, the reflection coefficients are estimated using
                                          x            ^                    =                                                    argmin                x                            ⁢                                                                                      y                    -                    Ax                                                                    2                2                                      +                          λ              ⁢                                                                  x                                                  p                p                                                    ,                            (        1        )            where λ is the regularization parameter. l1-regularization (i.e., p=1) incorporates the sparsity assumptions by approximating the minimum lo problem, which is to find the most sparse vector that fits the data model. Directly solving the l0-regularization problem is typically not even attempted because it is known to be non-deterministic polynomial-time hard (NP-hard), i.e., very processing intensive to solve. To date, l1-regularization has been the recommended approach for sparse radar image reconstruction.
So called l1-LS algorithms incorporate the sparsity assumption, generally give acceptable results, and could be made reasonably fast via speed-up techniques or parallel/distributed implementations. LS-based estimation can, however, be ineffective and biased in the presence of outliers in the data. This is a particular disadvantage, however, because in practical settings, the presence of outliers in measurements is to be expected.
More specifically, the l1-LS estimation method has been known for some time, wherein the concept has been popularized in the statistics and signal processing communities as the Least Absolute Selection and Shrinkage Operator (LASSO) and Basis Pursuit denoising, respectively. A number of iterative algorithms have been introduced for solving the l1-LS estimation problem. Classical approaches use linear programming or interior-point methods. However, in many real-world and large scale problems, these traditional approaches suffer from high computational cost and lack of estimation accuracy. Heuristic greedy alternatives like Orthogonal Matching Pursuit and Least Angle Regression (LARS) have also been proposed. These algorithms are also likely to fail when applied to real-world, large-scale problems. Several other types of algorithms for providing l1-LS estimates exist in the literature and others continue to be proposed.
Some of the shortcomings of the DAS and RSM algorithms may be attributed to the fact that their data model does not take into consideration known prior information about SOIs. Since only a few scatterers are present in a typical SOI, better reflection coefficient estimates can be expected when the a-priori sparsity assumption is incorporated into the model. The SLIM algorithm produces good results by incorporating the assumption the SOIs are sparsely populated by scatterers. However, its high computational cost may make the SLIM algorithm impractical for large-scale real time applications. The class of l1-regularized least squares (l1-LS) algorithms have been recommended for radar imaging where sparse solutions are expected. This class of algorithms have been found to perform well in a number of applications, such as machine learning and neuroimaging. In off-line applications, where training data is attainable, generalized cross-validation or similar techniques can be used to obtain optimal or near-optimal regularization parameter. However, in real-time on-line applications such as GPR imaging, there is no straightforward way to choose an appropriate regularization parameter. It may therefore be difficult to effectively take advantage of l1-LS algorithms in GPR imaging problems or other real-time applications.